/*
 * [6] 从尾到头打印链表
 * 方法：利用栈的后进先出特性
 * 如果可以改变链表结构，则可以先反转链表指针，在遍历输出即可，可以不用辅助空间
 *
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

// 回顾普通的二分查找
/**
int binarysearch(vector<int>& a, int k) {
  int left = 0;
  int right = a.size() - 1;
  int mid;
  while (left <= right) {
    mid = (left + right) / 2;
    // k较a[mid]大时，在右半区间查找
    if (a[mid] < k) left = mid + 1;
    // k较a[mid]小时，在右半区间查找
    else if (a[mid] > k)
      right = mid - 1;
    // 若相等则返回mid
    else
      return mid;
  }
  // 找不到时返回-1
  return -1；
}
**/

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

struct ListNode
{
  int val;
  struct ListNode* pnext;
  // ListNode(int x) : val(x), pnext(NULL)
  // {
  // }
};

class Solution
{
 public:
  vector<int> printListNodeFromTailToHead(ListNode* phead)
  {
    // 存放链表节点指针的栈，栈通过指针可以访问到其所指向的栈的内容
    stack<ListNode*> nodes;
    ListNode* p = phead;

    while (p != nullptr)
    {
      nodes.push(p);
      p = p->pnext;
    }

    vector<int> result;
    while (!nodes.empty())
    {
      p = nodes.top();
      result.push_back(p->val);
      nodes.pop();
    }

    return result;
  }

  size_t FindClosest(const std::vector<float>& vec, const float& val)
  {
    size_t found = 0;

    // 正常，vec.back()没有超过360度
    if (vec.front() < vec.back())
    {
      found = upper_bound(vec.begin(), vec.end(), val) - vec.begin();
    }
    else
    {
      found = vec.rend() - upper_bound(vec.rbegin(), vec.rend(), val);
    }
    if (found == 0)
    {
      return found;
    }
    if (found == vec.size())
    {
      return found - 1;
    }
    auto diff_next = std::abs(vec[found] - val);
    auto diff_prev = std::abs(val - vec[found - 1]);
    // 返回的found是递增序列vec中某元素的某一个序号
    return diff_next < diff_prev ? found : found - 1;
  }
};

int main()
{
  class Solution solute;
  float step = (-25 - 15) / 32.0;
  vector<float> _row_angles;
  for (size_t r = 0; r < 32; r++)
  {
    _row_angles.push_back(15 + step * r);
    cout << "_row_angles:" << _row_angles[r] << endl;
  }

  // size_t cols = 870;
  // for (size_t c = 0; c < cols; c++)
  // {
  //   _col_angles.push_back(_start_angle + _step * c);
  // }

  std::cout << solute.FindClosest(_row_angles, -25) << std::endl;
  ;

  /*
  ListNode* nodehead = new ListNode;

  ListNode* node1 = new ListNode();
  node1->val = 1;
  nodehead->pnext = node1;

  ListNode* node2 = new ListNode();
  node2->val = 2;
  node1->pnext = node2;
  node2->pnext = nullptr;

  vector<int> result = solute.printListNodeFromTailToHead(nodehead);
  delete nodehead;
  delete node1;
  delete node2;
  */

  return 0;
}

// @lc code=end
